ДНФ и СДНФ

**Литерал** — это формула вида $x$ или $\bar{x}$, где $x$ — переменная.

**Дизъюнктивная нормальная форма (ДНФ)** — это формула вида $\bigvee_{i=1}^n F_i$, $n \geqslant 1$, где: * $F_i = \bigwedge_{j=1}^{k_i} L_{ij}$, $L_{ij}$ — литерал, $k_i \geqslant 1$; * $F_i$ называют **элементарными конъюнкциями**. ДНФ — **иерархическая** формула: отрицание применяется только к переменным, конъюнкция — к литералам, дизъюнкция — к элементарным конъюнкциям.

ДНФ от $k$ переменных называется **совершенной ($k$-СДНФ)**, если: * все элементарные конъюнкции $F_i$ различны; * каждая $F_i$ состоит из $k$ литералов, соответствующих различным переменным.